import java.util.Arrays;
import java.util.Scanner;

public class Main {

    /**
     * 使用Kadane算法寻找最大子数组和
     * @param nums 整数数组
     * @return 最大子数组和
     */
    public static int findMaxSubarraySum(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // 对于每个元素，决定是将其加入当前子数组还是开始新的子数组
            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
            // 更新全局最大值
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        return maxSoFar;
    }

    /**
     * 从命令行读取整数数组
     * @return 用户输入的整数数组
     */
    public static int[] readArrayFromCommandLine() {
        Scanner scanner = new Scanner(System.in);

        System.out.println("请输入整数数组，元素之间用空格分隔：");
        String input = scanner.nextLine();

        // 分割输入字符串
        String[] parts = input.split("\\s+");
        int[] array = new int[parts.length];

        // 将字符串转换为整数
        for (int i = 0; i < parts.length; i++) {
            try {
                array[i] = Integer.parseInt(parts[i]);
            } catch (NumberFormatException e) {
                System.out.println("错误: '" + parts[i] + "' 不是有效的整数，将被视为0。");
                array[i] = 0;
            }
        }

        scanner.close();
        return array;
    }

    public static void main(String[] args) {
        System.out.println("=== 寻找最大子数组和 ===");

        // 如果通过命令行参数提供了数组
        if (args.length > 0) {
            try {
                int[] array = new int[args.length];
                for (int i = 0; i < args.length; i++) {
                    array[i] = Integer.parseInt(args[i]);
                }
                System.out.println("输入的数组: " + Arrays.toString(array));
                int maxSum = findMaxSubarraySum(array);
                System.out.println("最大子数组和: " + maxSum);
                return;
            } catch (NumberFormatException e) {
                System.out.println("命令行参数包含非整数，将切换到交互式输入模式。");
            }
        }

        // 交互式输入模式
        int[] array = readArrayFromCommandLine();
        System.out.println("输入的数组: " + Arrays.toString(array));

        int maxSum = findMaxSubarraySum(array);
        System.out.println("最大子数组和: " + maxSum);
    }
}